package com.yww.algorithm.sort;

import java.util.Arrays;

/**
 * @author yww
 * @description 插入排序
 * @since 2024/2/23 15:52
 */
public class InsertionSort {
    public static void sort(int[] arr) {
        doSort(arr);
    }

    /**
     * 迭代插入实现
     */
    private static void doSort(int[] arr) {
        for (int low = 1; low < arr.length; low++) {
            int inserted = arr[low];
            int j = low - 1;
            while (j >= 0 && arr[j] > inserted) {
                arr[j + 1] = arr[j];
                j--;
            }
            if (j != low - 1) {
                arr[j + 1] = inserted;
            }
        }
    }

    /**
     * 递归插入实现
     * 无序区间 [low, high]
     */
    private static void recur(int[] arr, int low, int high) {
        if (low > high) {
            return;
        }
        int i = low - 1;
        int inserted = arr[low];
        while (i >= 0 && arr[i] > inserted) {
            arr[i + 1] = arr[i];
            i--;
        }
        if (i != low - 1) {
            arr[i + 1] = inserted;
        }
        recur(arr, low + 1, high);
    }

    public static void main(String[] args) {
        int[] a = {6, 5, 4, 3, 2, 1};
        System.out.println(Arrays.toString(a));
        sort(a);
        System.out.println(Arrays.toString(a));
    }
}
